package com.hqq.exercise.stack_queue;

import java.util.Stack;

/**
 * MinStack 包含min函数的栈
 * 题目描述:
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数
 * 在该栈中，调用min、push及pop德尔时间复杂度都是O(1)
 * 思路:
 * 定义一个辅助栈和一个标识最小值的变量
 * 当一个数入栈时,将最小值也同时入栈
 * Created by heqianqian on 2017/8/13.
 */
public class MinStack {

    //数据栈
    private Stack<Integer> dataStack = new Stack<>();
    //辅助栈
    private Stack<Integer> assStack = new Stack<>();
    //最小值
    private int min;

    public void push(Integer num) {
        if (dataStack.isEmpty()) {//当栈为空时
            min = num;
            assStack.push(num);
        } else {//栈不为空时 进行比较
            if (num < min) {//如果当前入栈元素最小的话
                min = num;
                assStack.push(num);
            } else {
                assStack.push(min);
            }
        }
        dataStack.push(num);
    }

    public Integer pop() {
        assStack.pop();
        if (!assStack.empty()) {
            min = assStack.peek();
        }else{
            min = -1;
        }
        return dataStack.pop();
    }

    public Integer min() {
        return min;
    }

    public boolean isEmpty() {
        return dataStack.isEmpty();
    }

    public void printDataStack() {
        int size = dataStack.size();
        System.out.print("数据栈: ");
        for (int i = 0; i < dataStack.size(); i++) {
            System.out.print(dataStack.get(i) + " ");
        }
        System.out.println();
    }

    public void printAssistStack() {
        int size = assStack.size();
        System.out.print("辅助栈: ");
        for (int i = 0; i < assStack.size(); i++) {
            System.out.print(assStack.get(i) + " ");
        }
        System.out.println();
    }

    public void printMin() {
        System.out.println("最小值: " + min);
    }
}
